package 滑动窗口;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 找到字符串中所有字母异位词6 {
    //https://leetcode.cn/problems/find-all-anagrams-in-a-string/
    int i = 0;
    public static List<Integer> findAnagrams1(String s, String p) {
        int[] hash1 = new int[26], hash2 = new int[26];
        char[] pp = p.toCharArray();
        char[] ss = s.toCharArray();
        List<Integer> list = new LinkedList<>();
        for (char a : pp) {
            hash2[a - 97]++;
        }
        int left = 0, right = 0, n = p.length();
        while (right < s.length()) {
            hash1[ss[right] - 97]++;
            while (right - left + 1 > n) {
                hash1[ss[left++] - 97]--;
            }
            int i = 0;
            for (; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    break;
                }
            }
            if (i == 26) {
                list.add(left);
            }
            right++;
        }
        return list;
    }
    public static List<Integer> findAnagrams2(String s, String p) {
        int[] hash1 = new int[26], hash2 = new int[26];
        char[] pp = p.toCharArray();
        char[] ss = s.toCharArray();
        List<Integer> list = new LinkedList<>();
        for (char a : pp) {
            hash2[a - 'a']++;
        }
        int left = 0, right = 0, n = p.length(), count = 0;
        while (right < s.length()) {
            hash1[ss[right] - 97]++;
            if (hash1[ss[right] - 97] <= hash2[ss[right] - 97]) {
                count++;
            }
            while (right - left + 1 > n) {
                if (hash1[ss[left] - 97] <= hash2[ss[left] - 97]) {
                    count--;
                }
                hash1[ss[left] - 97]--;
                left++;
            }
            /*int i = 0;
            for (; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    break;
                }
            }
            if (i == 26) {
                list.add(left);
            }*/
            if (count == n) {
                list.add(left);
            }
            right++;
        }
        return list;
    }
    public static List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int hash1[] = new int[26];
        for (char ch : p) {
            hash1[ch - 'a']++;
        }

        int[] hash2 = new int[26];
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) {// 动作区间
                count++;
            }
            if (right - left + 1 > m) {
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--;
                }
            }
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }



    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        findAnagrams(s,p);
    }
}
